package dynamicProgramming.MatrixPathProblem;

/**
 * @author zxc
 * @date 2023/01/24 09:46
 **/

/**
 * 题目 ：路径的数目
 * 题目详述 ：
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * 提示：
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 109
 */
public class UniquePaths {
    /**
     * 思路 ：
     * 假设f(i,j)为机器人当前所在位置可能的路径数目;
     *
     * 状态转移方程 :
     * 1.考虑特殊情况
     * （1）当i == 0时，同时又由于机器人只能够向右/下走，所以f(0,j) == 1（只可能是机器人向右走，直至走到坐标(0,j)为止）
     * （2）当j == 0时，同时又由于机器人只能够向右/下走，所以f(i,0) == 1（只可能时机器人向下走，直至走到坐标(i,0)为止）
     * 2.考虑一般情况
     * 当i > 0 && j > 0时，则f(i,j) = f(i-1,j) + f(i,j-1);
     * ===> 可以大致理解为，要求去f(i,j),只需要在f(i-1,j)向右走一步 || f(i,j-1)向下走一步;
     * @param m
     * @param n
     * @return
     */
    // 递归代码实现
    public int uniquePaths(int m, int n) {
        // 由于要求取f(i,j)的话，只需要知道f(i-1,j) && f(i,j-1)即可;
        int [][] temp = new int[m][n];
        // 递归实现 ：即，f(i,j)为(i + 1) * (j + 1)大小网格的所以可能路线数量;
        return flushBack(m - 1, n - 1 , temp);
    }
    // flushBack方法 ：返回当前位置(i,j)到起点位置(0,0)的所以可能路线数量;
    private int flushBack(int i, int j, int[][] temp) {
        // 有且仅当当前temp数组元素为null时，进行回溯获取当前位置(i,j)的所以可能路径数目;
        if(temp[i][j] == 0){
            // 特殊情况 ：i == 0（即，机器人只能够向右边走） || j == 0（即，机器人只能够向下边走）
            if(i == 0 || j == 0){
                temp[i][j] = 1;
            }
            // 普通情况 ：即，f(i,j)可以从f(i-1,j)或者f(i,j-1)位置，进行右移/下移来道道指定位置;
            else {
                temp[i][j] = flushBack(i - 1,j,temp) + flushBack(i,j -1 ,temp);
            }
        }
        return temp[i][j];
    }
}
